package someTestExcemple.huaweiOd.divideAndRecursion;

//华为OD机试 - 篮球比赛 - 递归（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/142692017
import java.util.*;
public class BasketballGame {
    //最小差值
    private static int minDifValue = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] powers = new int[10];
        int sumPower =0;
        //10个篮球队员的能力
        for(int i=0;i<10;i++) {
            powers[i] = sc.nextInt();
            sumPower+=powers[i];
        }
        sc.close();
        //backtrack(powers, 0, 0, 0, sumPower);
        generateCombinations(0,0,new ArrayList<>(),powers,sumPower);
        System.out.println(minDifValue);

    }
    //回溯-暴力穷举所有可能
    private static void backtrack(int[] powers, int index, int teamAPower, int countA, int totalPower) {
        //说明已经遍历完所有元素
        if (index == powers.length) {
            if (countA == 5) {
                int teamBPower = totalPower - teamAPower;
                int diff = Math.abs(teamAPower - teamBPower);
                minDifValue = Math.min(minDifValue, diff);
            }
            //无论找不找得到找末尾都退出
            return;
        }
        // 尝试将当前球员加入 A 队
        backtrack(powers, index + 1, teamAPower + powers[index], countA + 1, totalPower);
        // 尝试不将当前球员加入 A 队
        backtrack(powers, index + 1, teamAPower, countA, totalPower);
    }

    /**
     * 递归生成所有从start开始的5人组合
     * @param start 当前选择的起始位置
     * @param count 已选择的人数
     * @param current 当前组合的索引列表
     */
    static void generateCombinations(int start, int count, List<Integer> current,int[] powers,int totalSum) {
        // 当选择了5个人时，计算差值
        if (count == 5) {
            int groupSum = 0;
            for (int index : current) {
                groupSum += powers[index];
            }
            int otherGroupSum = totalSum - groupSum;
            int diff = Math.abs(groupSum - otherGroupSum);
            if (diff < minDifValue) {
                minDifValue = diff;
            }
            return;
        }

        // 从当前起始位置到剩余位置选择
        for (int i = start; i < 10; i++) {
            current.add(i);
            //选择i号位置
            generateCombinations(i + 1, count + 1, current,powers,totalSum);
            //会朔
            current.remove(current.size() - 1); // 回溯 //当前位置i不选
        }
    }
}
